package com.sise.Linked;

/**
 *      剑指 Offer 24. 反转链表
 *
 *      输入: 1->2->3->4->5->NULL
 *      输出: 5->4->3->2->1->NULL
 */
public class _offer_24_reverseList {

    /**
     *      递归
     *      1、终止条件：当找到最后一个数值
     *      2、返回值：返回最后一个数值
     *      3、本次递归：将下一个节点指向自己 head.next.next = head，将自己指向空 head.next = null
     */
    public ListNode reverse(ListNode head){

        if (head == null || head.next == null) return head;
        ListNode last = reverse(head.next);                     // 由于 reverse() 不断递归，直到 head.next == null 进行返回，故此 last 就是最后一位数值 (5)，
                                                                // 这里传递的也是 head.next 而不是 head，保证当前值为 倒数第二个，5 -> 4 -> null
        head.next.next = head;                                  // head.next = 5，那么此时 head = 4，将 5 -> 4
        head.next = null;                                       // 再将 4 指向 null，不然此时依旧是 4 -> 5，为的就是断开这个链接
        return last;                                            // last 最后链表的最后值，直接返回即可
    }

    /**
     *      迭代：双指针
     *      https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/solution/fan-zhuan-lian-biao-yi-dong-de-shuang-zhi-zhen-jia/
     */
    public ListNode reverse2(ListNode head){

        // 一开始让 pre 指向 head（1），cur 为 null，说明 pre 在前一步
        ListNode pre = head;
        ListNode cur = null;
        while (pre != null){
            // 由于 pre 指向过后，那么原本的链接就断掉了，故此此时需要将 下一步的元素记录下来
            ListNode next = pre.next;
            pre.next = cur;     // pre 指向当前节点，反转
            cur = pre;          // 完成反转后，将 pre、cur 都往前移动一步
            pre = next;
        }
        return cur;
    }
}
